AtCoder Beginner Contest 321

321-like Checker

模拟。

public static void solve() {
    int n = io.nextInt();
    String s = String.valueOf(n);
    for (int i = 0; i < s.length() - 1; i++) {
        if (s.charAt(i) <= s.charAt(i + 1)) {
            io.println("No");
            return;
        }
    }
    io.println("Yes");
}

Cutoff

比赛时是暴力做的，赛后这个 \(O(1)\) 还想了半天。不多解释，代码还是比较好理解的。

public static void solve() {
    int n = io.nextInt(), x = io.nextInt();
    int min = 101, max = -1, sum = 0;
    for (int i = 0; i < n - 1; i++) {
        int t = io.nextInt();
        sum += t;
        min = Math.min(min, t);
        max = Math.max(max, t);
    }
    int t = x - (sum - min - max);
    if (t > max) {
        io.println(-1);
    } else {
        io.println(t <= min ? 0 : t);
    }
}

321-like Searcher

原来是使用十个二进制位来表示对应数字是否存在，通过暴力枚举算出所有可能的数，最后排序获取对应的位置即可，真的没想到。

public static void solve() {
    int k = io.nextInt();
    List<Long> ans = new ArrayList<>();
    for (int i = 2; i < 1 << 10; i++) {
        long x = 0L;
        for (int j = 9; j >= 0; j--) {
            if ((i >> j & 1) == 1) {
                x = x * 10 + j;
            }
        }
        ans.add(x);
    }
    Collections.sort(ans);
    io.println(ans.get(k - 1));
}

Set Menu

二分，状态真差，把加法和乘法混淆了。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), p = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b);
    long[] sum = new long[m + 1];
    for (int i = 0; i < m; i++) {
        sum[i + 1] = sum[i] + b[i];
    }
    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int x = p - a[i];
        int lo = 0, hi = m - 1;
        while (lo <= hi) {
            int mid= lo + (hi - lo) / 2;
            if (b[mid] <= x) lo = mid + 1;
            else hi = mid - 1;
        }
        ans += ((long) lo * a[i] + sum[lo]) + (long) (m - lo) * p;
    }
    io.println(ans);
}